package com.linyaonan.leetcode.medium._2476;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个 二叉搜索树 的根节点 root ，和一个由正整数组成、长度为 n 的数组 queries 。
 *
 * 请你找出一个长度为 n 的 二维 答案数组 answer ，其中 answer[i] = [mini, maxi] ：
 *
 * mini 是树中小于等于 queries[i] 的 最大值 。如果不存在这样的值，则使用 -1 代替。
 * maxi 是树中大于等于 queries[i] 的 最小值 。如果不存在这样的值，则使用 -1 代替。
 * 返回数组 answer 。
 *
 * 输入：root = [6,2,13,1,4,9,15,null,null,null,null,null,null,14], queries = [2,5,16]
 * 输出：[[2,2],[4,6],[15,-1]]
 * 解释：按下面的描述找出并返回查询的答案：
 * - 树中小于等于 2 的最大值是 2 ，且大于等于 2 的最小值也是 2 。所以第一个查询的答案是 [2,2] 。
 * - 树中小于等于 5 的最大值是 4 ，且大于等于 5 的最小值是 6 。所以第二个查询的答案是 [4,6] 。
 * - 树中小于等于 16 的最大值是 15 ，且大于等于 16 的最小值不存在。所以第三个查询的答案是 [15,-1] 。
 *
 * @author: Lin
 * @date: 2024/2/24
 */
public class ClosestNodesQueriesInABinarySearchTree {

    List<Integer> list = new ArrayList<>();

    public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {
        // 1. 边界

        // 2. 二叉搜索树变为升序数组
        dfs(root);

        // 3. 最右匹配小于等于，最左匹配大于等于
        List<List<Integer>> r = new ArrayList<>();
        for (Integer i : queries) {
            List<Integer> c = new ArrayList<>();
            c.add(rightLessOrEqual(i));
            c.add(leftMoreOrEqual(i));
            r.add(c);
        }

        return r;
    }

    public void dfs(TreeNode node) {
        if (node == null) {
            return;
        }

        dfs(node.left);
        list.add(node.val);
        dfs(node.right);

    }

    /**
     * 最右匹配小于等于数值，没有符合的返回-1
     * @param t
     * @return
     */
    public int rightLessOrEqual(int t) {
        int l = 0;
        int r = list.size() - 1;
        int result = -1;
        while (l <= r) {
            int m = (l + r) >>> 1;
            int numM = list.get(m);
            if (numM <= t) {
                result = numM;
                l = m + 1;
            } else {
                r = m - 1;
            }
        }

        return result;

    }

    /**
     * 最左匹配大于等于数值，没有符合的返回-1
     * @param t
     * @return
     */
    public int leftMoreOrEqual(int t) {
        int l = 0;
        int r = list.size() - 1;
        int result = -1;
        while (l <= r) {
            int m = (l + r) >>> 1;
            int numM = list.get(m);
            if (numM >= t) {
                result = numM;
                r = m - 1;
            } else {
                l = m + 1;
            }
        }

        return result;
    }

}
